:两人分别在房间 的概率。初始状态
注意当后继状态的 相等时不能转移。房间 相遇的概率即为 。
直接高斯消元即可,时间复杂度 。
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
#define eps 1e-8
template<typename _T>
void Read( _T &x ) {
x = 0; char s = getchar();
for( ; s < '0' || s > '9' ; s = getchar() );
for( ; s >= '0' && s <= '9' ; s = getchar() ) x = x * 10 + s - '0';
}
template<typename _T>
void Write( _T x ) {
if( x >= 10 ) Write( x / 10 );
putchar( x % 10 + '0' );
}
const int MAXN = 22;
int n , m , w , deg[ MAXN + 5 ]; double p[ MAXN + 5 ];
bool Graph[ MAXN + 5 ][ MAXN + 5 ];
double a[ MAXN * MAXN + 5 ][ MAXN * MAXN + 5 ];
int hs( int x , int y ) { return ( x - 1 ) * n + y; }
void print( ) {
printf("------");
for( int i = 1 ; i <= w ; i ++ )
for( int j = 1 ; j <= w + 1 ; j ++ )
printf("%.2f%c", a[ i ][ j ] , j == w + 1 ? '\n' : ' ' );
printf("--------");
}
void Gauss( ) {
for( int i = 1 ; i <= w ; i ++ ) {
int pos = i;
for( int j = i + 1 ; j <= w ; j ++ )
if( fabs( a[ j ][ i ] ) > fabs( a[ pos ][ i ] ) ) pos = j;
swap( a[ pos ] , a[ i ] );
if( fabs( a[ i ][ i ] ) < eps ) continue;
for( int j = 1 ; j <= w ; j ++ )
if( i != j ) {
double d = a[ j ][ i ] / a[ i ][ i ];
for( int k = i ; k <= w + 1 ; k ++ )
a[ j ][ k ] -= a[ i ][ k ] * d;
}
}
for( int i = 1 ; i <= w ; i ++ ) a[ i ][ m + 1 ] /= a[ i ][ i ];
}
int x , y;
int main( ) {
scanf("%d %d %d %d",&n,&m,&x,&y);
for( int i = 1 , u , v ; i <= m ; i ++ ) {
scanf("%d %d",&u,&v); deg[ u ] ++ , deg[ v ] ++;
Graph[ u ][ v ] = Graph[ v ][ u ] = 1;
}
for( int i = 1 ; i <= n ; i ++ ) scanf("%lf",&p[ i ]);
w = n * n;
a[ hs( x , y ) ][ w + 1 ] = 1;
for( int i = 1 ; i <= n ; i ++ )
for( int j = 1 ; j <= n ; j ++ ) {
a[ hs( i , j ) ][ hs( i , j ) ] = 1 - ( i == j ? 0 : p[ i ] * p[ j ] );
for( int u = 1 ; u <= n ; u ++ )
for( int v = 1 ; v <= n ; v ++ )
if( u != v && Graph[ i ][ u ] && Graph[ j ][ v ] )
a[ hs( i , j ) ][ hs( u , v ) ] = - ( 1 - p[ u ] ) / deg[ u ] * ( 1 - p[ v ] ) / deg[ v ];
for( int u = 1 ; u <= n ; u ++ )
if( u != j && Graph[ i ][ u ] )
a[ hs( i , j ) ][ hs( u , j ) ] = - ( 1 - p[ u ] ) / deg[ u ] * p[ j ];
for( int v = 1 ; v <= n ; v ++ )
if( i != v && Graph[ j ][ v ] )
a[ hs( i , j ) ][ hs( i , v ) ] = - p[ i ] * ( 1 - p[ v ] ) / deg[ v ];
}
Gauss();
for( int i = 1 ; i <= n ; i ++ ) printf("%.9f\n", a[ hs( i , i ) ][ w + 1 ] );
return 0;
}